This invention relates to the field of communication systems, and in particular to networks and network management.
Routers are used in networks to forward messages from one node to another in the network until the message reaches its intended destination. Routers use “forwarding tables”, or “routing tables” to facilitate the determination of the appropriate node to forward each message. For ease of reference, the term ‘router’ is used herein to refer to any device or system that is used to forward messages based on an address associated with the communication, including communication switches and the like. In like manner, the terms ‘forwarding table’ or ‘routing table’ are used herein to refer to any directives or indices that the router uses to select a communication path for each message or group of messages, regardless of whether these directives or indices are in the form of a table, and include, for example, virtual routing tables, forwarding information bases (FIBs), and so on.
FIG. 1A illustrates an example network, and FIG. 1B illustrates an example set of forwarding tables corresponding to this network. In this example, circles are used to indicate routers, and squares are used to indicate destination sub-networks. As illustrated in FIG. 1B, each entry in each router's forwarding table includes a prefix 110, a source protocol 120, a next hop 130, and a metric 140. In the example forwarding table, symbols A-H are used to indicate the addresses of the routers, and W-Z are used to indicate the sub-network prefix addresses. In an actual forwarding table, actual addresses, such as an IP address, would appear. In like manner, the symbol P is used to indicate a protocol, although the actual protocol, such as “OSPF” or “BGP” would appear in an actual forwarding table. Other information may also appear in a forwarding table.
The prefix 110 is the network address corresponding to a range of destination addresses. The source protocol 120 is the communication protocol for use of this entry in the forwarding table. The next hop 130 identifies the router to which the message will be transmitted if this entry is used. The metric 140 identifies the “cost” associated with transmitting the message to the destination if this entry is used. In the example of FIG. 1A, the links between routers include a figure that represents the example cost of communicating a message unit between the routers. For example, to send a message unit between routers A and B, the cost is “1”, whereas to send a message between routers A and F, the cost is “2”. Also in this example, the cost of communications between a sub-network and its supporting router is assumed to be zero.
Typically, each router broadcasts its forwarding table to each of its neighbors. The receiving router updates its forwarding table based on the entries of each of the received other forwarding tables. The cost of using each route in a neighbor's forwarding table is determined from the neighbor's metric entry 140, plus the cost of reaching that neighbor. If the received network prefix 110 is not in the receiving router's forwarding table, it is added, using this determined cost as the metric 140, and an identifier of the neighbor that provided this entry as the next hop 130. If the network prefix 110 is already in the receiving router's forwarding table, the newly created entry replaces the existing entry if the metric 140 of the new entry is less than the metric 140 of the existing entry. Optionally, a router may be configured to maintain multiple forwarding table entries for the same destination, using additional criteria beyond the metric 140.
Once a network is established, all of the forwarding tables achieve a ‘steady state’ condition, wherein each router includes the lowest cost routing entry for each destination reachable by the router. This steady state does not change unless and until a change occurs in the network. Such changes may be intentional or unintentional, where unintentional changes include mistaken or unintentional reconfigurations of routing parameters, undetected component or link failures, and so on. For ease of reference, purposeful changes that are not reported to or recorded by a network manager, or other party responsible for monitoring network performance, are considered unintentional changes. Forwarding table changes caused by intentional or unintentional changes to the network can lead to degradations in network performance, but because of the dynamics associated with propagating forwarding table entries throughout a network, the cause of such degradation is often difficult to determine.
It is an objective of this invention to facilitate the diagnosis of network performance changes. It is a further objective of this invention to facilitate the identification of the source or cause of a network change. It is a further objective of this invention to facilitate an identification of the originator(s) of detected differences in routing forwarding tables in the network.
These objectives and others are achieved by a method and system that compares the forwarding tables associated with routers in two versions of a network to identify changes. The method and system facilitate the identification of routers that are likely to be the cause of the differences in these forwarding tables. Each destination sub-network prefix is processed to identify all the routers that exhibit differences in their forwarding table for this prefix. Each router exhibiting a difference is assessed to determine whether the difference may have been propagated to this router from another router. If the difference could not have been propagated from another router, the router is identified as a potential source of the observed difference. By eliminating routers that could have received the effects of the differences from another router, the task of identifying the root cause of the observed differences is substantially reduced in complexity.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.